In the communications field, network equipment, such as routers and switches, are utilized for establishing a connection between multiple networks. The network equipment carries out communications by sending and receiving data, referred to as frames, based on layer 2 MAC and layer 3 IP based packets. Hereafter, one data unit will be to be referred to as a packet. The network equipment investigates the destination address of the received packet, determines the transfer destination of that packet, repeatedly 3 transfers packets to the specified transfer destination, and conveys the packet to the target destination. With the overall volume of packets that are being sent and received on networks worldwide greatly expanding, the packet transfer performance of network equipment must also be improved to keep pace with the increasing amount of traffic. Better transfer performance involves not simply transferring the packet, but also providing processing for transferring only those packets conforming to established rules (filtering), limiting the packet transfer volume to within a specified amount per unit of time in compliance with rules (shaping), sending packets after establishing an order of priority among packets conforming to rules, and correcting packet information in compliance with the rules, etc.
The Ethernet is utilized as an inexpensive network medium. Up until the mid 1990's, the speed of the Ethernet was a comparatively slow 10 Mbps, (Megabit per second) to 100 Mbps so that software processing utilizing a general-purpose processor was sufficient for packet processing. However, in the latter 1990's, the Ethernet speed increased to high speeds from 1 Gbps (Gigabit per second) to 10 Gbps. To process packets at these speeds, the network equipment utilized ASIC, as well as dedicated network processors designed solely for packet processing.
As network interface speeds increase, the time available for processing one packet is becoming shorter. Multiple processors (packet processing engines) are built into the network processors, and, by processing the packets in parallel, they obtain a processing time for each packet and improve the packet throughput. However, raising the network processor throughput and utilizing even faster high-speed network interfaces requires techniques to increase the number of packet processing engines inside the network processor. Using more packet processing engines makes the network processor size excessive and causes an increased power consumption.
Whereupon, a technology was proposed in JP-A No. 048730/2003 for expanding the cache memory, instead of increasing the number of internal packet processing engines, recording the processing results of the packet processing engine group in a cache referred to as a process cache, and providing network processor architecture for utilizing the process-cache contents for packets that can be handled with identical processing. This network processor architecture or architecture conforming to it hereinafter will be referred to as a cache-based packet processor. Packets possessing identical header information, for example, information where the source address and destination address are paired together in the header information, are prone to appear in large numbers within a short time (temporal locality) in the packet flow (traffic) on the network. Therefore, the cache-based packet processor is assumed to operate with comparative efficiency on middle mile networks positioned between the edge and the core of the network, and access networks and edge networks are positioned near the boundary of networks, where the extent of mixing in the packet flow is comparatively light.
When configuring network equipment from cache-based network processors, the cache-hit rate drops according to the arrival sequence of the packets, so that the throughput of the entire network equipment is likely to drop. More specifically, in some cases, a group made up of a large number of packets possessing identical headers will arrive within a short time, and registration of the initial packet in the cache is not completed before the arrival of the following packets.
Packet scheduling is required in order to resolve the above-mentioned problem. The known art contains many effective scheduling techniques. For example, a method is disclosed in domestic announcement No. 2001-519129 for implementing a first level of scheduling that sorts multiple sessions (flows) into classes, and then implements a second level of scheduling to match the several outputs from the first level, and then implements a third level of scheduling by ranking the outputs from the first and second levels in an order of priority. A method is disclosed in JP-A No. 185501/2002 for connecting the output queues and priority-ordered queues in vertical rows, and the priority queue in the prior stage places low priority packets on hold and attaches a mark to them, and, in the latter stage queues, it searches for congestion and, when detected, discards those low priority packets attached with a mark to maintain a fixed bandwidth for each priority level, regardless of fluctuations in traffic volume, so as to effectively utilize the guaranteed bandwidth.
A method is also disclosed in JP-A No. 101637/2000 comprising multiple queues for storing packets, and a scheduler implements transfer bandwidth control, weighting the lead (beginning) packet of each queue per transfer sequence in the order of fastest estimated transfer completion time. However, this method has the problem in that only a comparatively small number of queues can be mounted in the hardware. A method disclosed in JP-A No. 324471/2003 implements scheduling by arraying multiple processors in parallel and operating by time-sharing, in order to increase the number of mountable queues and achieve highly precise bandwidth control. However, none of the above-described scheduling methods is capable of implementing scheduling to prevent a drop in hit rate in the process cache, which is the problem resolved by this invention. The JP-B No. 346519/2003 application made by the present inventors, discloses a scheduling method in which, for a function block for processing packets missed in the cache, the processor only processes the lead packet in the flow with a cache miss, and cache misses from the second flow onward are held in the function block. However, the scheduling method of packets at a prior stage of accessing the process cache is not described.